//电话号码的字母组合
class Solution {
    vector<string> ret;
    string path;
    vector<string> tele = {{""},    {""},    {"abc"},  {"def"}, {"ghi"},
                           {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}};

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
        return ret;
        dfs(digits, 0);
        return ret;
    }
    void dfs(string& digits, int pos) {
        if (path.size() == digits.size()) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < tele[digits[pos] - '0'].size(); i++) {
            path.push_back(tele[digits[pos] - '0'][i]);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
};

//二叉树中的最大路径和
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
    int ret = INT_MIN;

public:
    int maxPathSum(TreeNode* root) {

        dfs(root);
        return ret;
    }
    int dfs(TreeNode* root) {
        if (!root)
            return 0;

        int l = max(dfs(root->left), 0);
        int r = max(dfs(root->right), 0);

        int t = root->val + l + r;
        ret = max(ret, t);
        return max(l, r) + root->val;
    }
};